package com.algorithm;

import com.google.common.collect.ComparisonChain;

import java.util.*;

/**
 * @author: sun.hongliang
 * @create: 2019/12/09 10:28
 */
public class TopKFrequentTest {
    public static void main(String[] args) {
        List<St> result = new ArrayList<>();
        ArrayList<St> result1 = new ArrayList<>();
        ArrayList<St> result2 = new ArrayList<>();
        result.add(new St(5));
        result.add(new St(2));
        result.add(new St(3));
        result.add(new St(4));
        Comparator<St> fc = TopKFrequentTest::feedCompator;
        Collections.sort(result, fc);

        System.out.println(result);
        System.out.println(fc.compare(new St(2), new St(3)));
    }

    private static int feedCompator(St o1, St o2) {
        return ComparisonChain.start().compare(o2.getScore(), o1.getScore()).result();
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(countMap::get));
        Set<Map.Entry<Integer, Integer>> entries = countMap.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            int size = priorityQueue.size();
            if (size < k) {
                priorityQueue.offer(key);
            } else {
                Integer peek = priorityQueue.peek();
                if (value >= countMap.get(peek)) {
                    priorityQueue.poll();
                    priorityQueue.offer(key);
                }
            }
        }
        List<Integer> result = new ArrayList<>(k);
        for (int i = 0; i < k && !priorityQueue.isEmpty(); i++) {
            Integer poll = priorityQueue.poll();
            result.add(poll);
        }
        return result;
    }
}

class St {
    private int score;

    public St(int score) {
        this.score = score;
    }

    public int getScore() {
        return score;
    }

    public void setScore(int score) {
        this.score = score;
    }

    @Override
    public String toString() {
        return "St{" +
                "score=" + score +
                '}';
    }
}
